/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2014 President and Fellows of Harvard College
 * Copyright (c) 2012-2014 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#ifndef STRING_SLICE_HH
#define STRING_SLICE_HH 1
#include "str.hh"
#include <algorithm>
#include <assert.h>
#include <string.h>
class threadinfo;

/** @brief Provide access to T-typed slices of a string. */
template <typename T>
struct string_slice {
 private:
  union union_type {
    T x;
    char s[sizeof(T)];
    union_type(T x) : x(x) {}
  };

 public:
  typedef T type;

  /** @brief Size of T in bytes. */
  static constexpr int size = (int)sizeof(T);

  /** @brief Return a T containing data from a string's prefix. */
  static T make(const char *s, int len) {
    if (len <= 0) return 0;
#if HAVE_UNALIGNED_ACCESS
    if (len >= size) return *reinterpret_cast<const T *>(s);
#endif
    union_type u(0);
    memcpy(u.s, s, std::min(len, size));
    return u.x;
  }

  /** @brief Return a T that compares similarly to a string's prefix.

      If a = make_comparable(s1, l1), b = make_comparable(s2, l2), and
      a < b, then the string (s1, l1) is lexicographically less than
      the string (s2, l2). Similarly, if a > b, then (s1, l1) is
      lexicographically greater than (s2, l2). If a == b, then the
      prefixes of (s1, l1) and (s2, l2) are lexicographically equal. */
  static T make_comparable(const char *s, int len) {
    return net_to_host_order(make(s, len));
  }

  /** @brief Return a T containing data from a string's prefix.
      @pre It is safe to access characters in the range
        [@a s - size - 1, @a s + size).

      This function acts like make(), but can use single memory accesses for
      short strings. These accesses may observe data outside the range [@a
      s, @a s + len). */
  static T make_sloppy(const char *s, int len) {
    if (len <= 0) return 0;
#if HAVE_UNALIGNED_ACCESS
    if (len >= size) return *reinterpret_cast<const T *>(s);
#if WORDS_BIGENDIAN
    return *reinterpret_cast<const T *>(s) & (~T(0) << (8 * (size - len)));
#elif WORDS_BIGENDIAN_SET
    return *reinterpret_cast<const T *>(s - (size - len)) >> (8 * (size - len));
#else
#error "WORDS_BIGENDIAN has not been set!"
#endif
#else
    union_type u(0);
    memcpy(u.s, s, std::min(len, size));
    return u.x;
#endif
  }

  /** @brief Return a T that compares similarly to a string's prefix.
      @pre It is safe to access characters in the range
        [@a s - size - 1, @a s + size).

      This function acts like make_comparable(), but can use single memory
      accesses for short strings. These accesses may observe data outside
      the range [@a s, @a s + len). */
  static T make_comparable_sloppy(const char *s, int len) {
    return net_to_host_order(make_sloppy(s, len));
  }

  /** @brief Unparse a comparable @a value into a buffer.
      @return Number of characters unparsed (<= buflen).

      If @a value was created by string_slice::make_comparable(s, x), then
      after this function returns, @a buf contains a string equal to the
      original @a s, except that trailing null characters have been
      removed. */
  static int unparse_comparable(char *buf, int buflen, T value) {
    union_type u(host_to_net_order(value));
    int l = size;
    while (l > 0 && u.s[l - 1] == 0) --l;
    l = std::min(l, buflen);
    memcpy(buf, u.s, l);
    return l;
  }

  /** @brief Unparse a comparable @a value into a buffer.
      @return Number of characters unparsed (<= buflen).

      If @a value was created by string_slice::make_comparable(s, @a len),
      then after this function returns, @a buf contains a string equal to
      the first @a len bytes of s. */
  static int unparse_comparable(char *buf, int buflen, T value, int len) {
    union_type u(host_to_net_order(value));
    int l = std::min(std::min(len, size), buflen);
    memcpy(buf, u.s, l);
    return l;
  }

  /** @brief Test two strings for equality.
      @param a first string
      @param b second string
      @param len number of characters in @a a and @a b
      @return true iff the two strings' first @a len characters are equal
      @pre It is safe to access characters in the ranges
        [@a a - size + 1, @a a + size) and [@a b - size + 1, @a b + size).

      Always returns the same result as "memcmp(@a a, @a b, @a len) == 0",
      but can be faster on some machines. */
  static bool equals_sloppy(const char *a, const char *b, int len) {
#if HAVE_UNALIGNED_ACCESS
    if (len <= size) {
      typename std::make_unsigned<T>::type delta =
          *reinterpret_cast<const T *>(a) ^ *reinterpret_cast<const T *>(b);
      if (unlikely(len <= 0)) return true;
#if WORDS_BIGENDIAN
      return (delta >> (8 * (size - len))) == 0;
#else
      return (delta << (8 * (size - len))) == 0;
#endif
    }
#endif
    return memcmp(a, b, len) == 0;
  }
};

template <typename T>
constexpr int string_slice<T>::size;

#endif

